//
// Created by xili on 2024/7/30 18:55.
// Go big or go home.
//
#include <iostream>
#include <vector>
#include <iostream>
#include <vector>

#define MAXSIZE 20001
using namespace std;

class Trie {
public:
    Trie() {
        tree.resize(MAXSIZE, vector<int>(26, 0));
        pass.resize(MAXSIZE, 0);
        en.resize(MAXSIZE, 0);
        cnts = 1;  // 从1开始
    }

    void insert(string word) {
        int cur = 1;
        pass[cur]++;
        for (char c: word) {
            int path = c - 'a';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnts;
            }
            cur = tree[cur][path];
            pass[cur]++;
        }
        en[cur]++;
    }

    bool search(string word) {
        int cur = 1;
        for (char c: word) {
            int path = c - 'a';
            if (tree[cur][path] == 0) {
                return false;
            }
            cur = tree[cur][path];
        }
        return en[cur] > 0;
    }

    bool startsWith(string prefix) {
        int cur = 1;
        for (char c: prefix) {
            int path = c - 'a';
            if (tree[cur][path] == 0) {
                return false;
            }
            cur = tree[cur][path];
        }
        return true;
    }

private:
    vector<vector<int>> tree;
    vector<int> pass;
    vector<int> en;
    int cnts;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */